#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&-(x))
#define mod 999999999
using namespace std;
ll s[4015][4015],n,q,a,b,c,d,tag,tr[4015][4015];
void add(int u,ll x,ll* tree){for(;u<=n;u+=lowbit(u))tree[u]+=x;}
ll sum(int u,ll* tree){ll re=0;for(;u;u-=lowbit(u))re+=tree[u];return re;}
struct fastin{
	char c[1<<23],*bg=NULL,*ed=NULL;
	char getchar(){
		if(bg==ed)ed=(bg=c)+fread(c,1,sizeof(c),stdin);
		return (bg==ed?EOF:*(bg++));
	}
	fastin& operator>>(ll &x){
		x=0;
		char u=getchar();
		while(u<'0'||u>'9')u=getchar();
		while(u>='0'&&u<='9')x=(x<<3)+(x<<1)+(u^'0'),u=getchar();
		return *this;
	}
}fin;
#define cin fin
int main(){
	ios::sync_with_stdio(0);
  	freopen("fire.in","r",stdin);
  	freopen("fire.out","w",stdout);
	cin>>n>>q;
	while(q--){
		cin>>tag;
		if(tag==2){
			cin>>a>>b;
			ll x=0;
			for(int i=1;i<=a;i++)x+=sum(b,tr[i]);
			cout<<x<<'\n';
			continue;
		}
		cin>>a>>b>>c>>d;
		if(c==4&&d>=mod)d-=mod;
		if(a==0){
			if(c==1)for(int i=1;i<=n;i++)s[b][i]&=d;
			if(c==2)for(int i=1;i<=n;i++)s[b][i]|=d;
			if(c==3)for(int i=1;i<=n;i++)s[b][i]^=d;
			if(c==4)for(int i=1;i<=n;i++)s[b][i]=(s[b][i]+d)%mod;
			for(int i=1;i<=n;i++)tr[b][i]=s[b][i];
			for(int i=1;i<=n;i++)if(i+lowbit(i)<=n)tr[b][i+lowbit(i)]+=tr[b][i];
		}
		if(a==1){
			if(c==1)for(int i=1;i<=n;i++)add(b,(s[i][b]&d)-s[i][b],tr[i]),s[i][b]&=d;
			if(c==2)for(int i=1;i<=n;i++)add(b,(s[i][b]|d)-s[i][b],tr[i]),s[i][b]|=d;
			if(c==3)for(int i=1;i<=n;i++)add(b,(s[i][b]^d)-s[i][b],tr[i]),s[i][b]^=d;
			if(c==4)for(int i=1;i<=n;i++)add(b,(s[i][b]+d)%mod-s[i][b],tr[i]),s[i][b]=(s[i][b]+d)%mod;
		}
	}
}
